package com.demo.java.OD201_250.OD232;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【至少需要多少个快递主站点 | 快递业务站】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145932480
 */
public class OdMain {

    public static int[][] matrix;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();  // 读取站点数量
        matrix = new int[num][num];   // 初始化矩阵，表示各站点间的连接关系
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                matrix[i][j] = scanner.nextInt();  // 填充矩阵
            }
        }

        Set<Integer> visited = new HashSet<>();  // 用于记录已访问的站点
        int count = 0;  // 主站点的数量，等同于连通分量的数量

        // 遍历所有站点
        for (int i = 0; i < num; i++) {
            if (!visited.contains(i)) {  // 如果当前站点未被访问
                Set<Integer> connectedNodes = new HashSet<>();  // 存储当前连通分量的站点
                connectedNodes.add(i);
                dfs(connectedNodes, i);  // 深度优先遍历
                visited.addAll(connectedNodes);  // 将该连通分量的所有站点标记为已访问
                count++;  // 增加主站点数
            }
        }

        System.out.println(count);  // 输出所需的主站点数量
    }

    // 深度优先遍历函数
    private static void dfs(Set<Integer> connectedNodes, int currentNode) {
        for (int i = 0; i < matrix.length; i++) {
            // 跳过已访问的节点或当前节点
            if (connectedNodes.contains(i) || i == currentNode) {
                continue;
            }
            // 如果当前节点与其他节点相连，则递归遍历
            if (matrix[currentNode][i] == 1) {
                connectedNodes.add(i);
                dfs(connectedNodes, i);
            }
        }
    }
}